package graph

import "gitee.com/kklt1996/data-structure/common"

/*
	使用邻接表的形式表示稀疏图
	邻接表的表示方式能表达自环边，但是不能以O(1)的方式处理平行边
*/
type SparseGraph struct {
	// 顶点的数量
	n int
	// 边的数量
	m int
	// 是否是有向图
	directed bool
	// 边的表示
	g [][]int
}

/*
	顶点数量
*/
func (graph SparseGraph) V() int {
	return graph.n
}

/*
	边的数量
*/
func (graph SparseGraph) E() int {
	return graph.m
}

/*
	添加边
	无法以O(1)的方式处理平行边的问题
*/
func (graph *SparseGraph) AddEdge(v int, w int) {
	// 添加边，无法解决平行边问题
	graph.g[v] = append(graph.g[v], w)
	// v != w 是为了解决当次添加的自环边问题
	if v != w && !graph.directed {
		graph.g[w] = append(graph.g[w], v)
	}
	graph.m++
}

/*
	检查边是否存在 O(n)
*/
func (graph SparseGraph) hasEdge(v int, w int) bool {
	for i := 0; i < len(graph.g[v]); i++ {
		if graph.g[v][i] == w {
			return true
		}
	}
	return false
}

/*
	获取某一个顶点相邻顶点的迭代器
*/
func (graph *SparseGraph) VertexIterator(v int) common.ForIntIterator {
	iterator := &SparseVertexIterator{0, v, graph}
	return iterator
}

type SparseVertexIterator struct {
	// 遍历的index
	index int

	// 需要遍历的顶点v
	v int

	// 图结构
	graph *SparseGraph
}

func (iterator *SparseVertexIterator) Begin() int {
	iterator.index = 0
	if iterator.index < len(iterator.graph.g[iterator.v]) {
		return iterator.graph.g[iterator.v][iterator.index]
	}
	return -1
}

func (iterator *SparseVertexIterator) Next() int {
	iterator.index++
	if iterator.index < len(iterator.graph.g[iterator.v]) {
		// 获取下一个值
		return iterator.graph.g[iterator.v][iterator.index]
	}
	return -1
}

func (iterator *SparseVertexIterator) End() bool {
	return iterator.index >= len(iterator.graph.g[iterator.v])
}
